/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-04-04
 * Time:11:05
 */
//307. 区域和检索 - 数组可修改
//给你一个数组 nums ，请你完成两类查询。
//其中一类查询要求 更新 数组 nums 下标对应的值
//另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right
    /**
     * 树状数组 - b站可搜
     * lowbit(x) = x & -x;
     * 1 的二进制 0001 其lowbit(x) = 1;
     * 2 -------0010  lowbit(x)= 10;
     * 3 -------0011  lowbit(x)= 1;
     * 4 -------0100  lowbit(x) = 100;
     * */
class NumArray {
    int[] tree;
    int[] Nums;
    int n;

    int lowbit(int x) {
        return x & -x;
    }

    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) {
            tree[i] += u;
        }
    }

    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            ans += tree[i];
        }
        return ans;
    }

    public NumArray(int[] nums) {
        Nums = nums;
        n = nums.length;
        tree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            add(i + 1, Nums[i]);
        }
    }

    public void update(int index, int val) {
        add(index + 1, val - Nums[index]);
        Nums[index] = val;
    }

    public int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }
}

public class TestDemo {


}
